package codeTop;

/**
 * 区08
 *
 * @author 雨凡
 * @version 区08.java, v0.1
 * @date 2025/07/05/12:57
 */
public class q208 {
    class Trie {

        class TrieNode{
            char letter;
            TrieNode[] next;
            boolean endFlag;
            public TrieNode(){

            }
            public TrieNode(char letter){
                this.letter = letter;
                this.next = new TrieNode[26];
                endFlag = false;
            }
        }
        TrieNode root;

        public Trie() {
            root = new TrieNode(' ');
        }

        public void insert(String word) {
            TrieNode p = root;
            for (int i = 0; i < word.length(); i++) {
                if (p.next[word.charAt(i) - 'a'] == null) {
                    p.next[word.charAt(i) - 'a'] = new TrieNode(word.charAt(i));
                }
                p = p.next[word.charAt(i)-'a'];
            }
            p.endFlag = true;
        }

        public boolean search(String word) {
            TrieNode p = root;
            for (int i = 0; i < word.length(); i++) {
                if (p.next[word.charAt(i) - 'a'] == null) {
                    return false;
                }
                p = p.next[word.charAt(i)-'a'];
            }
            return p.endFlag;
        }

        public boolean startsWith(String prefix) {
            TrieNode p = root;
            for (int i = 0; i < prefix.length(); i++) {
                if (p.next[prefix.charAt(i) - 'a'] == null) {
                    return false;
                }
                p = p.next[prefix.charAt(i)-'a'];
            }
            return true;
        }
    }
}
